home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 13794 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.9 KB  |  75 lines
  1. Path: news.ichange.com!newsmaster
  2. From: Jesse Liberty <jl@staff.ichange.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: NEWBIE : Quicksort
  5. Date: Wed, 27 Mar 1996 07:24:26 -0500
  6. Organization: AT&T
  7. Message-ID: <3159337A.2DB5@staff.ichange.com>
  8. References: <Pine.SOL.3.91.960324135520.8433A-100000@orion> <4j4ruf$gf4@news1.h1.usa.pipeline.com> <Pine.SOL.3.91.960325221334.202B-100000@orion>
  9. NNTP-Posting-Host: 140.244.99.60
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0 (Win95; I)
  14. CC: jl@staff.ichange.com
  15.  
  16. FRANCO wrote:
  17. > 
  18. > On 25 Mar 1996, Pete Grant wrote:
  19. > 
  20. > >    int n = sizeof(z) / sizeof(int);
  21. > >    qsort(z, n, sizeof(int), comp);
  22. > >    for (int i = 0; i < n; i++)
  23. > >       cout << ' ' << z[i];
  24. > 
  25. > Pete,
  26. > 
  27. > Can this be done without using qsort from the standard library <stdlib.h>?
  28.  
  29. Sure, in my book Teach Yourself MORE C++ In 21 Days I show how to write a number of sorts, quicksort among them. Here's the 
  30. basic code. 
  31.  
  32.     template <class T>
  33.     void myQuickSort(T* Input, int left, int right)
  34.     {
  35.        if (right > left)
  36.        {
  37.           T target = Input[right-1];
  38.           int i = left-1;
  39.           int x = right-1;
  40.           for (;;)
  41.           {
  42.              while (*Input[++i] < *target)
  43.              ;
  44.              while (*Input[--x] > *target)
  45.              ;
  46.  
  47.              if (i >= x)
  48.                 break;
  49.              Swap(Input[i], Input[x]);
  50.           }
  51.  
  52.           Swap(Input[i], Input[right-1]);
  53.           myQuickSort(Input,left,i);
  54.           myQuickSort(Input,i+1,right);
  55.  
  56.        }
  57.     }
  58.  
  59.     template <class T>
  60.     inline void Swap(T& i, T& j)
  61.     {
  62.        T temp;
  63.        temp = j;
  64.        j = i;
  65.        i = temp;
  66.     }
  67.  
  68. ------
  69. Jesse Liberty [AT&T New Media Services]
  70. jl@staff.ichange.com    ZDNet: 72241,72
  71. Teach Yourself C++ In 21 Days. Sams 1994
  72. Teach Yourself MORE C++ In 21 Days. Sams 1996
  73. Teach Yourself ANSI C++ In 21 Days. Sams 1996
  74. C++: An Introduction To Programming. Que 1996
  75.